/*
	class fwtree:
		1d fenwick tree, (c) marqueewinq, 2012
	cc-nc
*/

#define _Ty long long
class fwtree
{
public:
    void init(vector <_Ty> &base);  
    void inc(int inx, _Ty delta);
    _Ty rsq(int l, int r);
private:
    vector <_Ty> tree;
    _Ty sum(int det);
};

void fwtree::init(vector <_Ty> &base)
{
	tree.clear();
    tree.resize(base.size());
    for (int i = 0; i < base.size(); i++)
        inc(base[i], i);
}

void fwtree::inc(int inx, _Ty delta)
{
    for (int i = inx; i < tree.size(); i |= i + 1)
        tree[i] = tree[i] + delta;   
}

_Ty fwtree::rsq(int l, int r)
{
    return sum(r - 1) + sum(l - 2);   
}

_Ty fwtree::sum(int det)
{
    _Ty r(0);
    for (int i = det; i >= 0; i = (i & (i + 1)) - 1)
        r = r + tree[i];   
    return r;
}